﻿using System;
using System.Diagnostics;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ExpressionLanguage
{
    public class ExpressionParser
    {
        public class AstNode
        {
            public enum NodeType
            {
                ARITHMETIC,
                UNARY,
                VARIABLE,
                CONSTANT,
                FUNCTION_CALL,
                ASSIGNMENT,
                BRANCH,
                SCOPE ,
                OBJECT,
                NULL
            }

            public NodeType Type
            {
                get { return Type_; }
            }

            protected AstNode(NodeType type)
            {
                Type_ = type;
            }

            private NodeType Type_;
        }

        internal class AstNode_Null : AstNode
        {
            public AstNode_Null()
                : base(AstNode.NodeType.NULL)
            { }
        }

        internal class AstNode_Arithmetic : AstNode
        {
            public AstNode_Arithmetic(ExpressionScanner.LexInfo lexinfo)
                : base(AstNode.NodeType.ARITHMETIC)
            {
                Operator_ = lexinfo;
            }

            public AstNode LeftChild
            {
                get { return LeftChild_; }
                set { LeftChild_ = value; }
            }

            public AstNode RightChild
            {
                get { return RightChild_; }
                set { RightChild_ = value; }
            }

            public ExpressionScanner.LexInfo Operator
            {
                get { return Operator_; }
                set { Operator_ = value; }
            }

            private ExpressionScanner.LexInfo Operator_;
            private AstNode LeftChild_, RightChild_;
        }

        internal class AstNode_Variable : AstNode
        {
            public AstNode_Variable(ExpressionScanner.LexInfo lexinfo)
                : base(AstNode.NodeType.VARIABLE)
            {
                Variable_ = lexinfo;
            }

            public ExpressionScanner.LexInfo Variable
            {
                get { return Variable_; }
            }

            private ExpressionScanner.LexInfo Variable_;
        }

        internal class AstNode_Constant : AstNode
        {
            public AstNode_Constant(ExpressionScanner.LexInfo lexinfo)
                : base(AstNode.NodeType.CONSTANT)
            {
                Constant_ = lexinfo;
            }

            public ExpressionScanner.LexInfo Constant
            {
                get { return Constant_; }
            }

            private ExpressionScanner.LexInfo Constant_;
        }

        internal class AstNode_FunctionCall : AstNode
        {
            public AstNode_FunctionCall(ExpressionScanner.LexInfo functionName)
                : base(AstNode.NodeType.FUNCTION_CALL)
            {
                FunctionName_ = functionName;
                FunctionParameter_ = new List<AstNode>();
            }

            public void AddParameter(AstNode node)
            {
                FunctionParameter_.Add(node);
            }

            public List<AstNode> Parameters
            {
                get { return FunctionParameter_; }
            }

            public ExpressionScanner.LexInfo FunctionName
            {
                get { return FunctionName_; }
            }

            private ExpressionScanner.LexInfo FunctionName_;
            private List<AstNode> FunctionParameter_ = new List<AstNode>();
        }

        internal class AstNode_Assignment : AstNode
        {
            public AstNode_Assignment()
                : base(AstNode.NodeType.ASSIGNMENT)
            { }


            public ExpressionScanner.LexInfo Left
            {
                get { return Left_; }
                set { Left_ = value; }
            }

            public AstNode Right
            {
                get { return Right_; }
                set { Right_ = value; }
            }

            private ExpressionScanner.LexInfo Left_;
            private AstNode Right_;
        }

        internal class AstNode_Unary : AstNode
        {
            public AstNode_Unary()
                : base(AstNode.NodeType.UNARY)
            { }

            public ExpressionScanner.LexInfo Operator
            {
                get { return Operator_; }
                set { Operator_ = value;}
            }

            public AstNode Operand
            {
                get { return Operand_;  }
                set { Operand_ = value; }
            }

            private AstNode Operand_;
            private ExpressionScanner.LexInfo Operator_;
        }

        internal class AstNode_Scope : AstNode 
        {
            public AstNode_Scope()
                : base(AstNode.NodeType.SCOPE)
            { }

            public AstNode_Scope( ExpressionScanner.LexInfo name )
                :this()
            {
                ScopeName_ = name;
            }

            public ExpressionScanner.LexInfo ScopeName 
            {
                get { return ScopeName_; }
                set { ScopeName_ = value;}
            }


            public List<AstNode> Code
            {
                get { return Code_; }
                set { Code_ = value; }
            }

            private List<AstNode> Code_;
            private ExpressionScanner.LexInfo ScopeName_;
        }

        internal class AstNode_Object : AstNode
        {
            public AstNode_Object():
                base(AstNode.NodeType.OBJECT)
            { }

            public List<AstNode> Code
            {
                get { return Code_; }
                set { Code_ = value;}
            }

            public ExpressionScanner.LexInfo ClassName
            {
                get { return ClassName_; }
                set { ClassName_ = value;}
            }

            public AstNode_FunctionCall Constructor
            {
                get { return Constructor_; }
                set { Constructor_ = value;}
            }

            public AstNode_FunctionCall PostInit
            {
                get { return PostInit_; }
                set { PostInit_ = value;}
            }

            private ExpressionScanner.LexInfo ClassName_;
            private AstNode_FunctionCall Constructor_;
            private AstNode_FunctionCall PostInit_;
            private List<AstNode> Code_;
        }

        internal class AstNode_Branch : AstNode 
        {
            public AstNode_Branch()
                : base(AstNode.NodeType.BRANCH)
            { }

            // In order to keep the data structure simple
            // We keep an AstNode_Null as place holder to
            // tell the executor that, this branch is a 
            // else branch instead of elif branch. A elif
            // branch is simple a code collections plus a
            // arithmetic node which indicates the evaluation
            // of true/false.
            public struct Branch
            {
                public List<AstNode> Code
                {
                    get;
                    set;
                }

                public AstNode Condition
                {
                    get;
                    set;
                }

                // Fast routine to grab a else branch
                public static Branch ElseBranch()
                {
                    Branch branch = new Branch();
                    branch.Code = new List<AstNode>();
                    branch.Condition = new AstNode_Null();
                    return branch;
                }
            }

            public List<Branch> Branches
            {
                get { return Branches_;  }
                set { Branches_ = value; }
            }

            public void AddBranch( Branch branch )
            {
                Branches_.Add(branch);
            }

            private List<Branch> Branches_ = new List<Branch>();
        }

        private static bool IsConstant(ExpressionScanner.LexInfo token)
        {
            switch (token.Token)
            {
                case ExpressionScanner.TToken.STRING:
                case ExpressionScanner.TToken.NUMBER:
                    return true;
                default:
                    return false;
            }
        }

        private static bool IsBinaryOperator(ExpressionScanner.LexInfo token)
        {
            switch (token.Token)
            {
                case ExpressionScanner.TToken.ADD:
                case ExpressionScanner.TToken.SUB:
                case ExpressionScanner.TToken.MUL:
                case ExpressionScanner.TToken.DIV:
                case ExpressionScanner.TToken.LT:
                case ExpressionScanner.TToken.LET:
                case ExpressionScanner.TToken.GT:
                case ExpressionScanner.TToken.GET:
                case ExpressionScanner.TToken.EQ:
                case ExpressionScanner.TToken.NEQ:
                case ExpressionScanner.TToken.AND:
                case ExpressionScanner.TToken.OR:
                    return true;
                default:
                    return false;
            }
        }

        private static bool IsUnaryOperator(ExpressionScanner.LexInfo token)
        {
            switch(token.Token)
            {
                case ExpressionScanner.TToken.NOT:
                case ExpressionScanner.TToken.SUB:
                    return true;
                default:
                    return false;
            }
        }

        private static bool IsHighPriorityOperator(ExpressionScanner.TToken leftToken, ExpressionScanner.TToken rightToken)
        {
            if (leftToken != ExpressionScanner.TToken.MUL || leftToken != ExpressionScanner.TToken.DIV)
                return (rightToken == ExpressionScanner.TToken.MUL) || (rightToken == ExpressionScanner.TToken.DIV);
            else
                return false;
        }

        private static AstNode ParseUnary(ExpressionScanner scanner , ErrorCollector collector,ExpressionScanner.LexInfo op)
        {
            Debug.Assert(IsUnaryOperator(op));
            AstNode_Unary unary = new AstNode_Unary();
            unary.Operator = op;
            unary.Operand = ParseOperand(scanner, collector);
            return unary;
        }

        // Parse operand should be able to detect unary operator negative operator.
        private static AstNode ParseOperand(ExpressionScanner scanner, ErrorCollector collector)
        {
            ExpressionScanner.LexInfo nextToken = scanner.Next();
            AstNode ret;

            if (nextToken.Token == ExpressionScanner.TToken.VARIABLE)
            {
                // Variable
                ExpressionScanner.LexInfo lookUp = scanner.Peek();
                if (lookUp.Token == ExpressionScanner.TToken.LEFT_BRACKET)
                {
                    // Function Call goes here
                    ret = ParseFunctionCall(scanner, nextToken, collector);
                    if (ret == null)
                    {
                        return null;
                    }
                }
                else
                {
                    // Just an variable 
                    ret = new AstNode_Variable(nextToken);
                    scanner.Move(nextToken);
                }
            }
            else if (nextToken.Token == ExpressionScanner.TToken.LEFT_BRACKET)
            {
                // Subexpression
                ret = ParseArithmetic(scanner, collector);
                // Error parsing the sub expression
                if (ret == null)
                {
                    return null;
                }
                // the last should be bracket
                nextToken = scanner.Next();
                Debug.Assert(nextToken.Token == ExpressionScanner.TToken.RIGHT_BRACKET);
            }
            else if (IsConstant(nextToken))
            {
                // Constant
                ret = new AstNode_Constant(nextToken);
            }
            else if(IsUnaryOperator(nextToken))
            {
                // Unary
                return ParseUnary(scanner, collector, nextToken);
            }
            else
            {
                collector.Message = "Unexpected token:" + ExpressionScanner.GetTokenName(nextToken.Token);
                return null;
            }
            return ret;
        }

        private static AstNode ParseArithmetic(ExpressionScanner scanner, ErrorCollector collector)
        {
            AstNode_Arithmetic root = null;
            AstNode left = ParseOperand(scanner, collector);
            if (left == null)
                return null;
            AstNode right = null;
            AstNode_Arithmetic parent = null;

            while (true)
            {
                // 1. Grab the operator node
                ExpressionScanner.LexInfo opToken = scanner.Peek();
                if (IsBinaryOperator(opToken))
                {
                    // Compare the priority here
                    if ( root != null && IsHighPriorityOperator(root.Operator.Token,opToken.Token) )
                    {
                        AstNode_Arithmetic highNode = new AstNode_Arithmetic(opToken);
                        highNode.LeftChild = root.RightChild;
                        root.RightChild = highNode;
                        parent = root;
                        root = highNode;
                    }
                    else
                    {
                        root = new AstNode_Arithmetic(opToken);
                        root.LeftChild = left;
                    }
                }
                else
                {
                    // Unknown end terminator, just return what we have right now
                    return left;
                }
                scanner.Move(opToken);

                right = ParseOperand(scanner, collector);
                if (right == null)
                {
                    return null;
                }
                root.RightChild = right;
                if (parent != null)
                {
                    parent.RightChild = root;
                    root = parent;
                    parent = null;
                }
                left = root;
            }
        }

        private static AstNode ParseRightHandValue(ExpressionScanner scanner, ErrorCollector collector)
        {
            ExpressionScanner.LexInfo nextToken = scanner.Peek();
            if( nextToken.Token == ExpressionScanner.TToken.NEW )
            {
                return ParseObject(scanner, collector);
            }
            return ParseArithmetic(scanner, collector);
        }

        private static AstNode ParseAssignment(ExpressionScanner scanner, ExpressionScanner.LexInfo variableName, ErrorCollector collector)
        {
            AstNode_Assignment assignment = new AstNode_Assignment();
            assignment.Left = variableName;
            ExpressionScanner.LexInfo nextToken = scanner.Peek();
            if (nextToken.Token != ExpressionScanner.TToken.ASSIGN)
            {
                collector.Message = "Not an assignment,expecting assignment!\nCode:\n" + nextToken.Slice;
                return null;
            }
            scanner.Move(nextToken);

            assignment.Right = ParseRightHandValue(scanner, collector);

            if (assignment.Right == null)
                return null;

            return assignment;
        }

        private static AstNode ParseFunctionCall(ExpressionScanner scanner, ExpressionScanner.LexInfo functionName, ErrorCollector collector)
        {
            ExpressionScanner.LexInfo nextToken = scanner.Peek();
            //CDebugger.Assert (nextToken.Token == CExpressionScanner.TToken.LEFT_BRACKET);
            scanner.Move(nextToken);
            AstNode_FunctionCall ret = new AstNode_FunctionCall(functionName);
            // Checking void call
            nextToken = scanner.Peek();
            if (nextToken.Token == ExpressionScanner.TToken.RIGHT_BRACKET)
            {
                scanner.Move(nextToken);
                return ret;
            }
            // Reaching here means that we need to parse the parameter lists
            while (true)
            {
                // 1. Parsing arithmetic expression 
                AstNode parameters = ParseRightHandValue(scanner, collector);
                if (parameters != null)
                {
                    // 2. Add parameters for function 
                    ret.AddParameter(parameters);
                    nextToken = scanner.Peek();
                    if (nextToken.Token == ExpressionScanner.TToken.RIGHT_BRACKET)
                    {
                        scanner.Move(nextToken);
                        return ret;
                    }
                    else if (nextToken.Token == ExpressionScanner.TToken.COMMA)
                    {
                        scanner.Move(nextToken);
                        continue;
                    }
                    else
                    {
                        collector.Message = "Unexpected token: " + ExpressionScanner.GetTokenName(nextToken.Token);
                        return null;
                    }
                }
                else
                {
                    return null;
                }
            }
        }

        private static AstNode ParseObjectConstructor(ExpressionScanner scanner,ErrorCollector collector)
        {
            ExpressionScanner.LexInfo nextToken = scanner.Next();
            if( nextToken.Token != ExpressionScanner.TToken.VARIABLE )
            {
                collector.Message = "The object constructor must be a function call.";
                return null;
            }
            AstNode ret = ParseFunctionCall(scanner, nextToken, collector);
            if (ret == null)
                return null;
            nextToken = scanner.Next();
            if (nextToken.Token != ExpressionScanner.TToken.END)
            {
                collector.Message = "Expecting \";\" here;";
                return null;
            }
            return ret;
        }

        private static AstNode ParseObjectPostInit(ExpressionScanner scanner,ErrorCollector collector)
        {
            ExpressionScanner.LexInfo nextToken = scanner.Next();
            if (nextToken.Token != ExpressionScanner.TToken.VARIABLE)
            {
                collector.Message = "The object post init must be a function call.";
                return null;
            }
            AstNode ret = ParseFunctionCall(scanner, nextToken, collector);
            if (ret == null)
                return null;
            nextToken = scanner.Next();
            if (nextToken.Token != ExpressionScanner.TToken.END)
            {
                collector.Message = "Expecting \";\" here;";
                return null;
            }
            return ret;
        }

        private static AstNode ParseObjectScope(ExpressionScanner scanner,AstNode_Object objNode,ErrorCollector collector)
        {
            ExpressionScanner.LexInfo nextToken = scanner.Next();
            if( nextToken.Token != ExpressionScanner.TToken.LEFT_SCOPE )
            {
                collector.Message = "Expecting { while initializing object.";
                return null;
            }
            objNode.Code = new List<AstNode>();
            while(true)
            {
                nextToken = scanner.Peek();

                switch (nextToken.Token)
                {
                    case ExpressionScanner.TToken.CTOR:
                        scanner.Move(nextToken);
                        if (objNode.Constructor == null)
                        {
                            AstNode func = ParseObjectConstructor(scanner, collector);
                            if (func == null)
                                return null;
                            objNode.Constructor = (AstNode_FunctionCall)func;
                        }
                        else
                        {
                            collector.Message = "The constructor is already existed.";
                            return null;
                        }
                        break;
                    case ExpressionScanner.TToken.POST:
                        scanner.Move(nextToken);
                        if (objNode.PostInit == null)
                        {
                            AstNode func = ParseObjectPostInit(scanner, collector);
                            if (func == null)
                                return null;
                            objNode.PostInit = (AstNode_FunctionCall)func;
                        }
                        else
                        {
                            collector.Message = "The post initialization is already existed.";
                            return null;
                        }
                        break;
                    case ExpressionScanner.TToken.RIGHT_SCOPE:
                        scanner.Move(nextToken);
                        return objNode;
                    default:
                        AstNode code = ParseStatement(scanner, collector);
                        if (code == null)
                            return null;
                        objNode.Code.Add(code);
                        break;
                }
            }
        }

        private static AstNode ParseObject(ExpressionScanner scanner,ErrorCollector collector)
        {
            ExpressionScanner.LexInfo nextToken = scanner.Next();
            Debug.Assert(nextToken.Token == ExpressionScanner.TToken.NEW);
            // 1. Parsing the class name
            nextToken = scanner.Next();
            if( nextToken.Token != ExpressionScanner.TToken.VARIABLE )
            {
                collector.Message = "Expecting a valid variable work as class name after \"new\"";
                return null;
            }
            AstNode_Object objNode = new AstNode_Object();
            objNode.ClassName = nextToken;
            if (ParseObjectScope(scanner, objNode, collector) == null)
                return null;
            return objNode;
        }

        private static AstNode ParseScope(ExpressionScanner scanner, ExpressionScanner.LexInfo scopeName, ErrorCollector collector)
        {
            ExpressionScanner.LexInfo nextToken = scanner.Peek();
            AstNode_Scope scope = new AstNode_Scope(scopeName);
            scope.Code = ParseScopeBody(scanner, collector);
            if (scope.Code == null)
                return null;
            return scope;
        }

        private static List<AstNode> ParseScopeBody( ExpressionScanner scanner , ErrorCollector collector )
        {
            List<AstNode> ret = new List<AstNode>();
            ExpressionScanner.LexInfo nextToken = scanner.Peek();
            if (nextToken.Token != ExpressionScanner.TToken.LEFT_SCOPE)
            {
                collector.Message = "Expecting { as scope indicator";
                return null;
            }
            scanner.Move(nextToken);
            // Now we need to parse the statement body
            while(true)
            {
                nextToken = scanner.Peek();
                if( nextToken.Token == ExpressionScanner.TToken.RIGHT_SCOPE )
                    break;
                // Parse each statement inside of the scope
                AstNode statement = ParseStatement(scanner, collector);
                if (statement == null)
                    return null;
                ret.Add(statement);
            }

            // If we reach here, we have a nextToken pointed to right scope
            Debug.Assert(nextToken.Token == ExpressionScanner.TToken.RIGHT_SCOPE);
            scanner.Move(nextToken);
            return ret;
        }

        private static AstNode ParseBranchStatement( ExpressionScanner scanner, ErrorCollector collector , ExpressionScanner.LexInfo ifinfo )
        {
            ExpressionScanner.LexInfo nextToken = scanner.Peek();
            // The next token must be '(' to indicates that it is a condition 
            if(nextToken.Token != ExpressionScanner.TToken.LEFT_BRACKET )
            {
                collector.Message = "Expect ( to initiate a condition statement.";
                return null;
            }
            scanner.Move(nextToken);
            AstNode_Branch.Branch branch = new AstNode_Branch.Branch();
            // Parsing condition statements
            branch.Condition = ParseArithmetic(scanner, collector);
            if (branch.Condition == null)
                return null;
            nextToken = scanner.Next();
            if (nextToken.Token != ExpressionScanner.TToken.RIGHT_BRACKET)
                return null;
            // Parsing scope code
            branch.Code = ParseScopeBody(scanner,collector);
            if (branch.Code == null)
                return null;
            // Initialize the branch node here
            AstNode_Branch branchNode = new AstNode_Branch();
            branchNode.AddBranch(branch);
            // elif/else branch parse
            while(true)
            {
                nextToken = scanner.Peek();
                if( nextToken.Token != ExpressionScanner.TToken.ELIF )
                    break;
                // It must be elif token chain
                scanner.Move(nextToken);
                nextToken = scanner.Next();
                if( nextToken.Token != ExpressionScanner.TToken.LEFT_BRACKET )
                {
                    collector.Message = "Expecting ( when parse else/elif condition.";
                    return null;
                }
                // Condition 
                branch.Condition = ParseArithmetic(scanner, collector);
                if (branch.Condition == null)
                    return null;
                nextToken = scanner.Next();
                if( nextToken.Token != ExpressionScanner.TToken.RIGHT_BRACKET )
                {
                    collector.Message = "Expecting ) as end of condition statement.";
                    return null;
                }
                // Related scope code
                branch.Code = ParseScopeBody(scanner, collector);
                if (branch.Code == null)
                    return null;
                branchNode.AddBranch(branch);
            }
            // Check if it is else condition
            nextToken = scanner.Peek();
            if (nextToken.Token != ExpressionScanner.TToken.ELSE)
                return branchNode;
            // We need to initialize an else branch and the condition node for that
            // else branch should be AstNode_Null to indicates no condition is used.
            branch = AstNode_Branch.Branch.ElseBranch();
            scanner.Move(nextToken);
            branch.Code = ParseScopeBody(scanner, collector);
            if (branch.Code == null)
                return null;
            branchNode.AddBranch(branch);
            return branchNode;
        }

        // A sentence is initialized as variable
        private static AstNode ParseSentence(ExpressionScanner scanner, ErrorCollector collector , ExpressionScanner.LexInfo variableInfo )
        {
            AstNode ret;
            ExpressionScanner.LexInfo lookUp = scanner.Peek();
            if (lookUp.Token == ExpressionScanner.TToken.LEFT_BRACKET)
            {
                ret = ParseFunctionCall(scanner, variableInfo, collector);
            }
            else if (lookUp.Token == ExpressionScanner.TToken.ASSIGN)
            {
                ret = ParseAssignment(scanner, variableInfo, collector);
            }
            else if(lookUp.Token == ExpressionScanner.TToken.LEFT_SCOPE)
            {
                ret = ParseScope(scanner, variableInfo , collector );
            }
            else
            {
                collector.Message = "Meaningless Code!\nCode:\n" + lookUp.Slice;
                return null;
            }

            if (ret == null)
                return null;

            ExpressionScanner.LexInfo end = scanner.Peek();

            if (end.Token != ExpressionScanner.TToken.END)
            {
                collector.Message = "Expected \";\" here!\nCode:\n" + end.Slice;
                return null;
            }
            else
            {
                scanner.Move(end);
                return ret;
            }
        }

        private static AstNode ParseStatement(ExpressionScanner scanner, ErrorCollector collector)
        {
            ExpressionScanner.LexInfo nextInfo = scanner.Next();
            switch(nextInfo.Token)
            {
                case ExpressionScanner.TToken.IF:
                    return ParseBranchStatement(scanner, collector, nextInfo);
                case ExpressionScanner.TToken.VARIABLE:
                    return ParseSentence(scanner, collector, nextInfo);
                default:
                    collector.Message = "Meaningless sentence!";
                    return null;
            }
        }

        public static List<AstNode> Compile(string script, ErrorCollector collector)
        {
            List<AstNode> ret = new List<AstNode>();
            ExpressionScanner scanner = new ExpressionScanner(script);
            ExpressionScanner.LexInfo next;
            do
            {
                next = scanner.Peek();
                if (next.Token == ExpressionScanner.TToken.EOF)
                    break;
                AstNode node = ParseStatement(scanner, collector);
                if (node != null)
                    ret.Add(node);
                else
                {
                    return null;
                }
                next = scanner.Peek();
            } while (true);

            return ret;
        }
    }
}
